package com.company.ljh.medium;

import com.company.ljh.utils.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @description:
 * 199. 二叉树的右视图
 * 中等
 * 894
 * 相关企业
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/5 10:42
 * @version:1.0
 */
public class 二叉树的右视图 {
    public List<Integer> rightSideView(TreeNode root) {
        //key为深度，Value为最左节点
        Map<Integer,TreeNode> map = new HashMap();
        traversalTree(root,0,map);
        List<Integer> result = new ArrayList();
        for(int i=1;i<=map.size();i++){
            result.add(map.get(i).val);
        }
        return result;

    }
    //深度优先遍历，使用前序遍历，并通过Map来保存值，最后的值会覆盖前一个值，最后保存的一定是当前层最右侧的元素
    public void traversalTree(TreeNode node,int depth,Map<Integer,TreeNode> map){
        if(node == null){
            return ;
        }
        depth++;
        //前序遍历
        map.put(depth,node);
        traversalTree(node.left,depth,map);
        traversalTree(node.right,depth,map);
    }
}
